﻿using System;
using System.Collections.Generic;
using GeoAPI.Geometries;
using YJKGridTopologyCal.Geometries;

namespace YJKGridTopologyCal.Index.KdTree
{
	public class KdTree<T> where T : class
	{
		public static Coordinate[] ToCoordinates(ICollection<KdNode<T>> kdnodes)
		{
			return KdTree<T>.ToCoordinates(kdnodes, false);
		}

		public static Coordinate[] ToCoordinates(ICollection<KdNode<T>> kdnodes, bool includeRepeated)
		{
			CoordinateList coordinateList = new CoordinateList();
			foreach (KdNode<T> kdNode in kdnodes)
			{
				int num = includeRepeated ? kdNode.Count : 1;
				for (int i = 0; i < num; i++)
				{
					coordinateList.Add(kdNode.Coordinate, true);
				}
			}
			return coordinateList.ToCoordinateArray();
		}

		public KdTree() : this(0.0)
		{
		}

		public KdTree(double tolerance)
		{
			this._tolerance = tolerance;
		}

		public bool IsEmpty
		{
			get
			{
				return this._root == null;
			}
		}

		internal KdNode<T> Root
		{
			get
			{
				return this._root;
			}
		}

		public KdNode<T> Insert(Coordinate p)
		{
			return this.Insert(p, default(T));
		}

		public KdNode<T> Insert(Coordinate p, T data)
		{
			if (this._root == null)
			{
				this._root = new KdNode<T>(p, data);
				return this._root;
			}
			if (this._tolerance > 0.0)
			{
				KdNode<T> kdNode = this.FindBestMatchNode(p);
				if (kdNode != null)
				{
					kdNode.Increment();
					return kdNode;
				}
			}
			return this.InsertExact(p, data);
		}

		private KdNode<T> FindBestMatchNode(Coordinate p)
		{
			KdTree<T>.BestMatchVisitor<T> bestMatchVisitor = new KdTree<T>.BestMatchVisitor<T>(p, this._tolerance);
			this.Query(bestMatchVisitor.QueryEnvelope(), bestMatchVisitor);
			return bestMatchVisitor.Node;
		}

		public KdNode<T> InsertExact(Coordinate p, T data)
		{
			KdNode<T> kdNode = this._root;
			KdNode<T> kdNode2 = this._root;
			bool flag = true;
			bool flag2 = true;
			while (kdNode != null)
			{
				if (kdNode != null && p.Distance(kdNode.Coordinate) <= this._tolerance)
				{
					kdNode.Increment();
					return kdNode;
				}
				if (flag)
				{
					flag2 = (p.X < kdNode.X);
				}
				else
				{
					flag2 = (p.Y < kdNode.Y);
				}
				kdNode2 = kdNode;
				kdNode = (flag2 ? kdNode.Left : kdNode.Right);
				flag = !flag;
			}
			this._numberOfNodes += 1L;
			KdNode<T> kdNode3 = new KdNode<T>(p, data);
			kdNode3.Left = null;
			kdNode3.Right = null;
			if (flag2)
			{
				kdNode2.Left = kdNode3;
			}
			else
			{
				kdNode2.Right = kdNode3;
			}
			return kdNode3;
		}

		private static void QueryNode(KdNode<T> currentNode, Envelope queryEnv, bool odd, IKdNodeVisitor<T> visitor)
		{
			if (currentNode == null)
			{
				return;
			}
			double num;
			double num2;
			double num3;
			if (odd)
			{
				num = queryEnv.MinX;
				num2 = queryEnv.MaxX;
				num3 = currentNode.X;
			}
			else
			{
				num = queryEnv.MinY;
				num2 = queryEnv.MaxY;
				num3 = currentNode.Y;
			}
			bool flag = num < num3;
			bool flag2 = num3 <= num2;
			if (flag)
			{
				KdTree<T>.QueryNode(currentNode.Left, queryEnv, !odd, visitor);
			}
			if (queryEnv.Contains(currentNode.Coordinate))
			{
				visitor.Visit(currentNode);
			}
			if (flag2)
			{
				KdTree<T>.QueryNode(currentNode.Right, queryEnv, !odd, visitor);
			}
		}

		public void Query(Envelope queryEnv, IKdNodeVisitor<T> visitor)
		{
			KdTree<T>.QueryNode(this._root, queryEnv, true, visitor);
		}

		public IList<KdNode<T>> Query(Envelope queryEnv)
		{
			List<KdNode<T>> result = new List<KdNode<T>>();
			KdTree<T>.QueryNode(this._root, queryEnv, true, new KdTree<T>.KdNodeVisitor<T>(result));
			return result;
		}

		public void Query(Envelope queryEnv, IList<KdNode<T>> result)
		{
			KdTree<T>.QueryNode(this._root, queryEnv, true, new KdTree<T>.KdNodeVisitor<T>(result));
		}

		private KdNode<T> _root;

		private long _numberOfNodes;

		private readonly double _tolerance;

		private class KdNodeVisitor<T> : IKdNodeVisitor<T> where T : class
		{
			public KdNodeVisitor(IList<KdNode<T>> result)
			{
				this._result = result;
			}

			public void Visit(KdNode<T> node)
			{
				this._result.Add(node);
			}

			private readonly IList<KdNode<T>> _result;
		}

		private class BestMatchVisitor<T> : IKdNodeVisitor<T> where T : class
		{
			public BestMatchVisitor(Coordinate p, double tolerance)
			{
				this.p = p;
				this.tolerance = tolerance;
			}

			public KdNode<T> Node
			{
				get
				{
					return this.matchNode;
				}
			}

			public Envelope QueryEnvelope()
			{
				Envelope envelope = new Envelope(this.p);
				envelope.ExpandBy(this.tolerance);
				return envelope;
			}

			public void Visit(KdNode<T> node)
			{
				double num = this.p.Distance(node.Coordinate);
				if (num > this.tolerance)
				{
					return;
				}
				bool flag = false;
				if (this.matchNode == null || num < this.matchDist || (this.matchNode != null && num == this.matchDist && node.Coordinate.CompareTo(this.matchNode.Coordinate) < 1))
				{
					flag = true;
				}
				if (flag)
				{
					this.matchNode = node;
					this.matchDist = num;
				}
			}

			private readonly double tolerance;

			private KdNode<T> matchNode;

			private double matchDist;

			private Coordinate p;
		}
	}
}
